#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
private:
    vector<vector<int>> ops = { {1,0},{-1,0},{0,1},{0,-1} };

    struct Point {
        int x, y;
        Point(int i,int j):x(i),y(j){}
    };

    void coloring(vector<vector<int>>& A) {
        int color = 2;
        int rows = A.size();
        int cols = A[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (A[i][j] != 1) continue;
                vector<Point> stack;
                stack.emplace_back(i, j);
                A[i][j] = color;
                while (!stack.empty()) {
                    Point p = stack.back();
                    stack.pop_back();
                    for (int k = 0; k < ops.size(); ++k) {
                        if (p.x + ops[k][0] < 0 || p.x + ops[k][0] >= rows ||
                            p.y + ops[k][1] < 0 || p.y + ops[k][1] >= cols)
                            continue;
                        if (A[p.x + ops[k][0]][p.y + ops[k][1]] == 1) {
                            A[p.x + ops[k][0]][p.y + ops[k][1]] = color;
                            stack.emplace_back(p.x + ops[k][0], p.y + ops[k][1]);
                        }
                    }
                }
                ++color;
            }
        }
    }

public:
    int shortestBridge(vector<vector<int>>& A) {
        coloring(A);
        queue<Point> queue_;
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < A[i].size(); ++j) 
                if (A[i][j] == 2)
                    queue_.emplace(i, j);
        }
        int depth = 0;
        int rows = A.size();
        int cols = A[0].size();
        while (!queue_.empty()) {
            int size = queue_.size();
            for (int i = 0; i < size; ++i) {
                auto p = queue_.front();
                queue_.pop();
                for (int k = 0; k < ops.size(); ++k) {
                    if (p.x + ops[k][0] < 0 || p.x + ops[k][0] >= rows ||
                        p.y + ops[k][1] < 0 || p.y + ops[k][1] >= cols)
                        continue;
                    int x = p.x + ops[k][0];
                    int y = p.y + ops[k][1];
                    if (A[x][y] == 3)
                        return depth;
                    else if (A[x][y] == 0) {
                        A[x][y] = 2;
                        queue_.emplace(x, y);
                    }
                }
            }
            ++depth;
        }
        return 1;
    }
};